package com.future;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Description: 377. 组合总和 Ⅳ
 * <p>
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 *
 * @author weiruibai.vendor
 * Date: 2023/1/13 17:27
 */
class Solution_377 {

    private static Solution_377 instance = new Solution_377();

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1};
        int target = 4;
        System.out.println(instance.combinationSum4(nums, target));
    }

    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        calcArraySumTarget(nums, 0, target, new ArrayList<Integer>());
        /**
         * 对数组repeat每个月元素进行重新排序才是最终的答案
         */
        return ans;
    }


    /**
     * 1 2 3
     * 1 3 2
     * 2 1 3
     * 2 3 1
     * 3 1 2
     * 3 2 1
     * 6种组合 3 * (3-1)
     * <p>
     * 1 2 2
     * 2 1 2
     * 2 2 1
     * 3*(2-1)
     * <p>
     * 1 2 2 3
     * 1 2 3 2
     * 1 3 2 2
     * 2 1 2 3
     * 2 1 3 2
     * 3 1 2 2
     * 3 2 1 2
     * 3 2 2 1
     * 4*(3-1)=8
     *
     * @param nums
     * @param i
     * @param rest
     * @param list
     */
    private void calcArraySumTarget(int[] nums, int i, int rest, List<Integer> list) {
        if (i == nums.length) {
            if (rest == 0) {
                List<Integer> tmpList = new ArrayList<>(list);
                if (repeat.add(tmpList)) {
                    ans++;
                }
            }
            return;
        }
        int val = nums[i];
        for (int zhang = 0; zhang * val <= rest; zhang++) {
            for (int j = 0; j < zhang; j++) {
                list.add(val);
            }
            calcArraySumTarget(nums, i + 1, rest - zhang * val, list);
            for (int j = 0; j < zhang; j++) {
                list.remove(list.size() - 1);
            }
        }
    }

    static int ans = 0;
    Set<List<Integer>> repeat = new HashSet<>();
}
